import java.util.*;

public class Main {
    /*
    OJ 合并两个有序链表
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode nullList = new ListNode(0);
        ListNode ret = nullList;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                nullList.next = list2;
                nullList = nullList.next;
                list2 = list2.next;
            }else {
                nullList.next = list1;
                nullList = nullList.next;
                list1 = list1.next;
            }
        }
        while (list1 != null) {
            nullList.next = list1;
            nullList = nullList.next;
            list1 = list1.next;
        }
        while (list2 != null) {
            nullList.next = list2;
            nullList = nullList.next;
            list2 = list2.next;
        }
        nullList.next = null;//把最后一个节点 的next置为null
        return ret.next;

    }
    /*
    奇偶链表
     */
    public ListNode oddEvenList(ListNode head) {
        ListNode cont1 = new ListNode();//奇数链表头
        ListNode r1 = cont1;//奇数指针
        ListNode cont2 = new ListNode();//偶数链表头
        ListNode r2 = cont2;//偶数指针

        ListNode cur = head;//遍历指针
        ListNode curNext = null;//标记下一个遍历的位置
        int run = 1;//下标
        while (cur != null) {
            curNext = cur.next;
            if (run % 2 != 0) {
                r1.next = cur;
                cur.next = null;
                r1 = r1.next;
            }else {
                r2.next = cur;
                cur.next = null;
                r2 = r2.next;
            }
            run++;
            cur = curNext;
        }
        r1.next = cont2.next;
        return cont1.next;
    }
    /*
    oj 排序链表
     */
    class Cmp implements Comparator<ListNode>{
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }
    public ListNode sortList(ListNode head) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Cmp());
        ListNode cur = head;
        while (cur != null) {
            ListNode cont = cur.next;
            cur.next = null;
            queue.offer(cur);
            cur = cont;
        }
        head = queue.poll();
        if (head == null) {
            return head;
        }
        cur = head;

        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
        }
        return head;
    }
    /*
    oj 两数相加
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode();
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        ListNode cur3 = ret;
        int cmp = 0;//进位符
        ListNode parent = ret;//记录前一个节点 (程序运行完后面会多一个节点,用来删除此节点)
        while (cur1 != null || cur2 != null || cmp != 0) {//cur1 和 cur2的长度可能不相同
            int cont = cmp;//当前位置的数字
            if (cur1 != null) {//判断是否为空
                cont += cur1.val;
            }
            if (cur2 != null) {
                cont += cur2.val;
            }

            if (cont > 9) {
                cur3.val = cont % 10;
                cmp = 1;
            }else {
                cmp = 0;
                cur3.val = cont;
            }


            if (cur1 != null) {
                cur1 = cur1.next;
            }
            if (cur2 != null) {
                cur2 = cur2.next;
            }
            if (cur3.next == null) {
                cur3.next = new ListNode();
            }
            parent = cur3;
            cur3 = cur3.next;
        }
        parent.next = null;//程序运行完后面会多一个节点,用来删除此节点
        return ret;
    }
    /*
    从链表中删去总和值为零的连续节点
     */
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode cur = head;
        ListNode ret = new ListNode();
        ret.next = cur;
        ListNode parent = ret;//父节点
        for (; cur != null ; cur = cur.next) {
            ListNode cur2 = cur;
            int sum = 0;
            while (cur2 != null) {
                sum += cur2.val;
                if (sum == 0) {
                    if (cur == ret.next) {//当删除的是第一个元素时
                        ret.next = cur2.next;
                    }else {
                        parent.next = cur2.next;
                    }
                }
                cur2 = cur2.next;
            }
            parent = cur;
        }

        return ret.next;

    }
    /*
    移除重复节点
     */
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode cur = head;
        HashSet<Integer> hashSet = new HashSet<>();
        hashSet.add(cur.val);
        while (cur.next != null) {
            if (hashSet.contains(cur.next.val)) {
                cur.next = cur.next.next;//删了之后 cur就不用再往后走了
                //因为此时cur的next是新接上去的,需要重新判断
            }else {
                hashSet.add(cur.next.val);
                cur = cur.next;
            }
        }

        return head;
    }
    /*
    图书整理1
     */
    public int[] reverseBookList(ListNode head) {
        ListNode cur = head;
        Stack<Integer> stack = new Stack<>();

        while (cur != null) {
            stack.add(cur.val);
            cur = cur.next;
        }
        int size = stack.size();//这里要用 变量记录一下 不能直接用
        //因为循环中 每次pop 的size都会减少
        int[] ret = new int[size];
        for (int i = 0; i < size; i++) {
            ret[i] = stack.pop();
        }
        return ret;
    }
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /*
    一年中第几天
     */
    public int dayOfYear(String date) {
        int year = Integer.parseInt(date.substring(0,4));//java中是左闭右开
        int month = Integer.parseInt(date.substring(5,7));
        int day = Integer.parseInt(date.substring(8,10));
        if (month == 1) {
            return day;
        }
        int sum = 0;
        boolean isLeaP = false;
        if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) {
            isLeaP = true;
        }
        switch(month-1) {
            case 11 :
                sum += 30;
            case 10 :
                sum += 31;
            case 9 :
                sum += 30;
            case 8 :
                sum += 31;
            case 7 :
                sum += 31;
            case 6 :
                sum += 30;
            case 5 :
                sum += 31;
            case 4 :
                sum += 30;
            case 3 :
                sum += 31;
            case 2 :
                if (isLeaP) {
                    sum += 29;
                }else {
                    sum += 28;
                }
            case 1 :
                sum += 31;
            case 0 :
                sum += day;
                return sum;
        }

        return year;
    }
    /*
    拼写单词
     */
    public int countCharacters(String[] words, String chars) {
        //哈希思想
        char[] arr = new char[26];
        int sum = 0;
        for (int i = 0; i < chars.length(); i++) {
            arr[chars.charAt(i)-'a']++;
        }
        for (String cont : words) {
            char[] array = Arrays.copyOf(arr,arr.length);
            boolean isTrue = true;//是否会拼写
            for (int i = 0; i < cont.length(); i++) {
                if (array[cont.charAt(i)-'a'] < 1) {
                    isTrue = false;
                    break;
                }
                array[cont.charAt(i)-'a']--;//注意chars中的每个字母只能用一次
            }
            if (isTrue) {
                sum += cont.length();
            }
        }
        return sum;
    }
    /*
    最后一块石头的重量
     */
    class IntCmp implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new IntCmp());
        for (int i = 0; i < stones.length; i++) {
            queue.add(stones[i]);
        }
        while (!queue.isEmpty()) {
            int x = queue.poll();
            if (queue.isEmpty()) {
                return x;
            }
            int y = queue.poll();
            if (x - y > 0) {
                queue.add(x - y);
            }
        }

        return 0;
    }
    /*
    oj 判定是否为字符重排
     */
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        //使用哈希思想
        char[] array = new char[26];
        for (int i = 0; i < s1.length(); i++) {
            array[s1.charAt(i) - 97]++;
        }
        for (int i = 0; i < s2.length(); i++) {
            if (array[s2.charAt(i) - 97] == 0) {//当s2字符串的某个字母少于s1时
                return false;
            }else {
                array[s2.charAt(i) - 97]--;
            }
        }
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            sum += array[0];
        }
        if (sum == 0) {
            return true;
        }else {
            return false;
        }

    }
    /*
    oj 第一个错误版本
     */
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        while (left < right) {//二分查找
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {//当前是错误的 往前走
                right = mid;//这里不能是 mid-1 因为此时只有两条语句 is 和 else
                //所以要把mid包括在内才行
            }else {//当前不是错误的 往后走
                left = mid + 1;
            }
        }
        return left;
    }
    public boolean isBadVersion(int mid) {//这个方法是oj中自带,在此只是防止报错
        return false;
    }
    /*
    oj 搜索插入位置
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {//二分查找 找到值接近target的附近
            int mid = left + (right - left)/2;
            if (target > nums[mid]) {
                left = mid + 1;
            }else if (target < nums[mid]) {
                right = mid - 1;
            }else {
                return mid;
            }
        }
        if (left < 0) {//防止二分查找中 让left 和 right越界了
            left = 0;
        }
        if (target > nums[left]) {
            return left + 1;
        }else {
            if (left == 0) {
                return 0;
            }
            if (target > nums[left - 1]) {//当比右边小 比左边大时
                return left;
            }
            return left - 1;//比右边小也比左边小
        }
    }
    /*
    oj 猜数字大小
     */
    public int guessNumber(int n) {
        int left = 1;
        int right = n;
        while (left <= right) {//二分查找

            int mid = left + (right - left) / 2;//这样可以防止大数据计算溢出

            int result = guess(mid);//获取猜测三种结果-1 1 0 (oj题中给出的方法)
            switch(result) {
                case -1:
                    right = mid - 1;
                    break;
                case 1:
                    left = mid + 1;
                    break;
                case 0:
                    return mid;
            }
        }
        return -1;
    }
    public static int guess(int ret) {//这里写此方法是 防止报错
        return ret;
    }
    /*
    oj 各位相加
     */
    public int addDigits(int num) {
        while (num > 9) {//当是单位数时退出循环

            int tmp = 0;//每一位之和
            while (num > 0) {
                tmp += num % 10;
                num /= 10;
            }
            num = tmp;
        }
        return num;
    }
    /*
    oj 丑数
     */
    public boolean isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        int[] array = {2, 3, 5};
        for (int i : array) {
            while (n % i == 0) {//看n中有没有 2 3 5 有的话就除
                n /= i;
            }
        }
        return n == 1;//剩下为1的话就表明是丑数
    }
    /*
    oj 快乐数
     */
    public boolean isHappy(int n) {
        //不是快乐数 的无限进行循环 会有相同的数,当有相同的数时,那么就不是快乐数
        Set<Integer> s = new TreeSet<>();
        int tmp = n;
        while (!s.contains(tmp)) {//判断set中是否有tmp
            s.add(tmp);
            int cont = 0;
            while (tmp > 0) {//每个位置的平方 之间的和
                cont += Math.pow(tmp % 10 , 2);
                tmp /= 10;
            }
            if (cont == 1) {
                return true;
            }
            tmp = cont;
        }
        return false;
    }
    /*
    罗马数字转整数
     */
    public int romanToInt(String s) {
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            switch(s.charAt(i)) {
                case 'I' :
                    if (i+1 < s.length()) {
                        if (s.charAt(i+1) == 'V') {
                            i++;
                            sum += 4;
                            break;
                        }else if (s.charAt(i+1) == 'X') {
                            i++;
                            sum += 9;
                            break;
                        }
                    }
                    sum += 1;
                    break;
                case 'V' :
                    sum += 5;
                    break;
                case 'X' :
                    if (i+1 < s.length()) {
                        if (s.charAt(i+1) == 'L') {
                            i++;
                            sum += 40;
                            break;
                        }else if (s.charAt(i+1) == 'C') {
                            i++;
                            sum += 90;
                            break;
                        }
                    }
                    sum += 10;
                    break;
                case 'L' :
                    sum += 50;
                    break;
                case 'C' :
                    if (i+1 < s.length()) {
                        if (s.charAt(i+1) == 'D') {
                            i++;
                            sum += 400;
                            break;
                        }else if (s.charAt(i+1) == 'M') {
                            i++;
                            sum += 900;
                            break;
                        }
                    }
                    sum += 100;
                    break;
                case 'D' :
                    sum += 500;
                    break;
                case 'M' :
                    sum += 1000;
                    break;
            }

        }
        return sum;
    }
    /*
    移除元素
    给你一个数组 nums 和一个值 val，
    你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度
     */
    public int removeElement(int[] nums, int val) {
        int left = 0;//有效数据存放的位置
        int right = 0;//遍历一遍数组,查找有效数据
        int len = nums.length;
        for (right = 0; right < len; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
    /*
    删除有序数组中的重复项
     */
    public int removeDuplicates(int[] nums) {
        int cmp = nums[0];
        int cont = 1;//有效数据在数组的位置
        for (int i = 1; i < nums.length; i++) {
            if (cmp == nums[i]) {
                continue;
            }else {
                cmp = nums[i];
                nums[cont] = nums[i];
                cont++;
            }
        }
        return cont;
    }
    /*
    给你一个句子s 和一个整数k ,请你将s截断,使截断后的句子仅含 前 k个单词。
    返回 截断 s后得到的句子。
     */
    public String truncateSentence(String s, int k) {
        if (k < 1) {
            return new String();
        }
        StringBuilder tmp = new StringBuilder();
        int i = 0;
        while (k > 0) {
            if (i < s.length() && s.charAt(i) != ' ') {
                tmp.append(s.charAt(i));
                i++;
            }else {
                k--;
                if (k == 0) {//当空格没有时则退出循环
                    break;
                }
                tmp.append(s.charAt(i));
                i++;//找到空格时, i也要自增,否则就会循环

            }
        }
        return tmp.toString();

    }
    //实现函数 int sqrt(int x).
    // 计算并返回 x 的平方根
    public int sqrt (int x) {
        // write code here
        if (x == 0) {
            return 0;
        }
        if (x <= 2) {
            return 1;
        }
        int left = 1;
        int right = x / 2;
        while(left < right) {
            //(right - left + 1) >> 1 是实际mid长度
            //但是前面还要有left 确定位置
            int mid = left + (right - left + 1) / 2;//求中间值
            int sqrtTemp = x / mid;//求出当前(伪)平方根
            if (sqrtTemp < mid) {//当前mid 较大
                right = mid - 1;//缩小右边范围
            }else {//当前mid较小
                left = mid;//缩小左边范围
            }
        }
        return left;
    }
    /*判断是否为回文字符串*/
    public boolean judge (String str) {
        // write code here
        int left = 0;
        int right = str.length() - 1;
        while(left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    public static void main(String[] args) {
    }
}